import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}
class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;
        Queue<int[]> queue = new LinkedList();
        //判断位于 board 边缘的'O',将其置为'N'
        for(int i = 0; i < m; i++){
            if(board[i][0] == 'O'){
                queue.offer(new int[]{i, 0});
                board[i][0] = 'N';
                while(!queue.isEmpty()){
                    int[] poll = queue.poll();
                    for(int k = 0; k < 4; k++){
                        int x = poll[0] + dx[k];
                        int y = poll[1] + dy[k];
                        if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){
                            board[x][y] = 'N';
                            queue.offer(new int[]{x, y});
                        }
                    }
                }
            }
            if( board[i][n - 1] == '0'){
                queue.offer(new int[]{i, n - 1});
                board[i][n - 1] = 'N';
                while(!queue.isEmpty()){
                    int[] poll = queue.poll();
                    for(int k = 0; k < 4; k++){
                        int x = poll[0] + dx[k];
                        int y = poll[1] + dy[k];
                        if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){
                            board[x][y] = 'N';
                            queue.offer(new int[]{x, y});
                        }
                    }
                }
            }
        }

        for(int i = 0; i < n; i++){
            if(board[0][i] == 'O'){
                queue.offer(new int[]{0, i});
                board[0][i] = 'N';
                while(!queue.isEmpty()){
                    int[] poll = queue.poll();
                    for(int k = 0; k < 4; k++){
                        int x = poll[0] + dx[k];
                        int y = poll[1] + dy[k];
                        if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){
                            board[x][y] = 'N';
                            queue.offer(new int[]{x, y});
                        }
                    }
                }
            }
            if( board[m - 1][i] == 'O'){
                queue.offer(new int[]{m - 1, i});
                board[m - 1][i] = 'N';
                while(!queue.isEmpty()){
                    int[] poll = queue.poll();
                    for(int k = 0; k < 4; k++){
                        int x = poll[0] + dx[k];
                        int y = poll[1] + dy[k];
                        if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){
                            board[x][y] = 'N';
                            queue.offer(new int[]{x, y});
                        }
                    }
                }
            }
        }
        queue.clear();
        for(int i = 1; i < m - 1; i++){
            for(int j = 1; j < n - 1; j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                    queue.offer(new int[]{i, j});
                    while(!queue.isEmpty()){
                        int[] poll = queue.poll();
                        for(int k = 0; k < 4; k++){
                            int x = poll[0] + dx[k];
                            int y = poll[1] + dy[k];
                            if(x > 0 && x < m - 1 && y > 0 &&
                                    y < n - 1 && board[x][y] == 'O'){
                                board[x][y] = 'X';
                                queue.offer(new int[]{x, y});
                            }
                        }
                    }
                }
            }
        }

        //将'N'置为'O'
        for(int i = 0; i < m ; i++){
            for(int j = 0; j < n ; j++) if(board[i][j] == 'N') board[i][j] = 'O';
        }
    }
}